/* 链式堆栈定义 */
typedef enum {false, true} bool;
typedef int SElemSet; /* 栈元素为数组下标 */
#define NILElem 0     /* 0下标表示空元素 */

typedef struct StackNode *Position; /* 指针即结点位置 */
struct StackNode {
    SElemSet data; /* 存储数据 */
    Position next; /* 链接栈中下一个元素的位置 */
};
typedef struct StackHeadNode *Stack;
struct StackHeadNode {
    int size; /* 链接栈中当前元素个数 */
    Position top; /* 链接栈的栈顶指针，初始化为NULL */
};

void InitStack(Stack stack) {
    /* 初始化一个空的链接栈 */
    stack->size = 0;
    stack->top = NULL;
}

bool IsEmpty(Stack stack) {
    /* 判断栈是否为空 */
    if (stack->size == 0)
        return true;
    else
        return false;
}

void Push(Stack stack, SElemSet x) {
    Position new_node;

    new_node = (Position)malloc(sizeof(struct StackNode));
    new_node->data = x;
    new_node->next = stack->top;
    stack->top = new_node;
    stack->size++;
}

SElemSet Top(Stack stack) {
    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
        return NILElem;
    } else {
        return stack->top->data;
    }
}

void Pop(Stack stack) {
    Position temp;

    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
    } else {
        temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
        stack->size--;
    }
}

void DestroyStack(Stack stack) {
    free(stack);
}
/* 堆栈定义结束*/

void Visit(BinaryTree tree, int idx) {
    printf("%c", tree->data[idx]);
}

bool NotNIL(BinaryTree tree, int idx) {
    /* 判断下标为idx的树结点是否非空结点 */
    return (idx <= tree->size && tree->data[idx] != NIL);
}

void PreOrder(BinaryTree tree) {
    Stack stack;
    int idx;

    stack = (Stack)malloc(sizeof(struct StackHeadNode));
    InitStack(stack); /* 初始化栈stack，用于存放结点 */
    idx = 1; /* 根结点位置 */
    while (NotNIL(tree, idx) == true || IsEmpty(stack) == false) {
        while (NotNIL(tree, idx) == true) { /* 当前结点不是空结点 */
            Visit(tree, idx); /* 访问结点 */
            Push(stack, idx); /* 结点下标压入栈 */
            idx <<= 1; /* 沿左分支下移 */
        }
        if (IsEmpty(stack) == false) { /* 如果栈不为空 */
            idx = Top(stack);
            Pop(stack); /* 弹出栈顶结点 */
            idx = (idx << 1) + 1; /* 移到右子树 */
        }
    }
    DestroyStack(stack);
}

void InOrder(BinaryTree tree) {
    Stack stack;
    int idx;

    stack = (Stack)malloc(sizeof(struct StackHeadNode));
    InitStack(stack); /* 初始化栈stack，用于存放结点 */
    idx = 1; /* 根结点位置 */
    while (NotNIL(tree, idx) == true || IsEmpty(stack) == false) {
        while (NotNIL(tree, idx) == true) { /* 当前结点不是空结点 */
            Push(stack, idx); /* 结点下标压入栈 */
            idx <<= 1; /* 沿左分支下移 */
        }
        if (IsEmpty(stack) == false) { /* 如果栈不为空 */
            idx = Top(stack);
            Visit(tree, idx); /* 访问结点 */
            Pop(stack); /* 弹出栈顶结点 */
            idx = (idx << 1) + 1; /* 移到右子树 */
        }
    }
    DestroyStack(stack);
}

void PostOrder(BinaryTree tree) {
    Stack stack;
    int idx, top, top_right, pre_top;

    stack = (Stack)malloc(sizeof(struct StackHeadNode));
    InitStack(stack); /* 初始化栈stack，用于存放结点 */
    idx = 1; /* 根结点位置 */
    while (NotNIL(tree, idx) == true || IsEmpty(stack) == false) {
        while (NotNIL(tree, idx) == true) { /* 当前结点不是空结点 */
            Push(stack, idx); /* 结点下标压入栈 */
            idx <<= 1; /* 沿左分支下移 */
        }
        top = Top(stack); /* stack非空，top指向栈顶结点 */
        top_right = (top << 1) + 1; /* top的右孩子下标 */
        pre_top = NILElem; /* 初始化pre_top */
        while (IsEmpty(stack) == false && (NotNIL(tree, top_right) == false
        || top_right == pre_top)) {
            Visit(tree, top); /* 访问当前栈顶结点 */
            pre_top = top; /* 栈顶结点传给pre_top */
            Pop(stack); /* 弹出栈顶结点 */
            if (IsEmpty(stack) == false) {
                top = Top(stack); /* 栈非空，top指向新的栈顶结点 */
            } else {
                top = NILElem; /* 空栈，top赋值为空 */
            }
            top_right = (top << 1) + 1; /* top的右孩子下标 */
        }
        if (top != NILElem) {
            idx = top_right; /* 移到栈顶结点的右子树并开始遍历 */
        }
    }
    DestroyStack(stack);
}